class Solution {
public:
    int dp[20][20];
    vector<vector<string>> ans;
    vector<string> temp;
    void compute_dp(string &s){
        memset(dp, 0, sizeof(int)*20*20);
        int n = s.size();
        for(int k=0; k<n; ++k){
            for(int i=0; i<n; ++i){
                if(k==0) dp[i][i] = 1;
                else if(k==1 && i+1<n && s[i]==s[i+1]) dp[i][i+1] = 1;
                else if(i+k<n && dp[i+1][i+k-1]==1 && s[i]==s[i+k]) dp[i][i+k]=1;
            }
        }
    }
    void dfs(int k, string &s, vector<string> &temp){
        if(k == s.size()) ans.push_back(temp);
        for(int i=1; i<=s.size(); ++i){
            if(i+k > s.size()) break;
            if(dp[k][k+i-1]==0) continue;
            temp.push_back(s.substr(k, i));
            dfs(k+i, s, temp);
            temp.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        compute_dp(s);
        dfs(0, s, temp);
        return ans;
    }
};